COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	The Pluto Landing
C00007 00003	_The Pluto Landing (Resumed)_
C00008 ENDMK
C⊗;
The Pluto Landing

An unmanned space craft will be launched soon, to arrive at Pluto in 1997.
Because radio communication to Pluto and back takes eight hours, earthbased
scientists will not be able to help the lander find a safe place to land.
However, a television camera aboard will survey the landing zone; the picture
it sees, as a series of black and white spots, will be stored in an array

	(IMAGE: ARRAY[1..1000, 1..1000]OF CHAR) 

for examination by the control program.

The lander, as seen from above, is shown below.















It must land in the orientation shown for the sake of its antennae and solar panels.
Because it is nearly a square, the safest place to land is at the center of the 
largest obstacle-free square region that can be found.  Because obstacles are
believed to be dark rocks projecting up through white ice, an obstacle-free region
in the array is made up of blanks; an obstacle is represented by an asterisk.

You have been hired to program the search for the best landing site.  Your 
predecessor proposed this algorithm:

(1) Do the steps below for all coordinates  X, Y from 1 to 1000.

(2) To find the largest blank square with (X,Y) as its northwest corner, try each
size in turn until one contains an obstacle.

(3) To check a particular size S, iterate  U from X to X + S-1, and V from Y to
Y + S-1, checking for IMAGE[U,V]='*'

Your predecessor was dismissed when a secretary typing the program noticed that the
program, given an image with one asterisk at (500,500), would try 10↑6 locations
X,Y; would try at least 250 sizes for the (X,Y) pairs in the regions shaded below;

















and would spend at least  1↑2 + 2↑2 3↑2 + ... + 250↑2 = about 250↑3/3 steps at each
(X,Y) of them, for a total of at least 10↑6 x 250↑3/3 steps through the inner loop
of the program.  At 10↑6 steps per second, the program would take five million
seconds, or ten weeks; the landing was expected to be over in 10 minutes.  The
first candidate to replace him suggested several ways to make the program faster,
such as testing the squares by adding layers







to already tested smaller squares.

Still, at each point (X,Y), on the average more than 250↑2 points were tested, for
a running time of 60000 seconds, or 16 hours.  You were hired because you were
someone's nephew, but you suspect that if your program requires more than a half
minute or so, you may be nobody's baby.  What should you do?  We will come back
to this problem later in this section; you may want to mull over it for an hour
or so before reading on.

_The Pluto Landing (Resumed)_

Solution:

For each point X,Y, you will compute and store as S[X,Y] the size of the largest
blank square region with (X,Y) as its upper left corner.  If IMAGE[X,Y] is '*',
then S[X,Y] is 0; otherwise, S[X,Y] is the smallest of {S[X+1,Y], S[X+1,Y+1],
S[X,Y+1]}, plus 1.  Doing the X and Y iterations in the decreasing direction,
th needed values have already been stored.  The algorithm also remembers the
location (XM,YM) where S[X,Y] was largest.  If the array is made one row oversized
and asterisks  are stored in the resulting border, no special tests need be made
for map edges.